{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Palindromic Subsequence II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestPalindromeSubseq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长回文子序列 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>字符串&nbsp;<code>s</code>&nbsp;的某个子序列符合下列条件时，称为“<strong>好的回文子序列</strong>”：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>它是&nbsp;<code>s</code>&nbsp;的子序列。</li>\n",
    "\t<li>它是回文序列（反转后与原序列相等）。</li>\n",
    "\t<li>长度为<strong>偶数</strong>。</li>\n",
    "\t<li>除中间的两个字符外，其余任意两个连续字符不相等。</li>\n",
    "</ul>\n",
    "\n",
    "<p>例如，若&nbsp;<code>s = \"abcabcabb\"</code>，则&nbsp;<code>\"abba\"</code>&nbsp;可称为“好的回文子序列”，而&nbsp;<code>\"bcb\"</code>&nbsp;（长度不是偶数）和&nbsp;<code>\"bbbb\"</code>&nbsp;（含有相等的连续字符）不能称为“好的回文子序列”。</p>\n",
    "\n",
    "<p>给定一个字符串&nbsp;<code>s</code>， 返回<em>&nbsp;</em><code>s</code>&nbsp;的<strong>最长“好的回文子序列”</strong>的<strong>长度</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"bbabab\"\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> s 的最长“好的回文子序列”是 \"baab\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"dcbccacdb\"\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> s 的最长“好的回文子序列”是 \"dccd\"。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 250</code></li>\n",
    "\t<li><code>s</code>&nbsp;包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-palindromic-subsequence-ii](https://leetcode.cn/problems/longest-palindromic-subsequence-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-palindromic-subsequence-ii](https://leetcode.cn/problems/longest-palindromic-subsequence-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"bbabab\"', '\"dcbccacdb\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0, ''] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            prev = [0, '']\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if s[i] == s[j] and s[i] != prev[1]:\n",
    "                    prev, dp[j] = dp[j], [prev[0] + 2, s[i]]\n",
    "                else:\n",
    "                    prev = dp[j]\n",
    "                    if dp[j + 1][0] > dp[j][0]:\n",
    "                        dp[j] = dp[j + 1]\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "from functools import lru_cache\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        ind = defaultdict(list)\n",
    "        for i, va in enumerate(s):\n",
    "            ind[va].append(i)\n",
    "\n",
    "        # 记忆化搜索\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            res = 2\n",
    "            for r in range(x + 1, y):\n",
    "                if s[r] != s[x]:\n",
    "                    val = s[r]\n",
    "                    right = -1\n",
    "                    for rj in ind[val][::-1]:\n",
    "                        if rj < y:\n",
    "                            right = rj\n",
    "                            break\n",
    "\n",
    "                    left = -1\n",
    "                    for li in ind[val]:\n",
    "                        if li > x:\n",
    "                            left = li\n",
    "                            break\n",
    "\n",
    "                    if left < right and left != -1 and right != -1:\n",
    "                        res = max(res, 2 + dfs(left, right))\n",
    "\n",
    "            return res\n",
    "            \n",
    "\n",
    "        # 枚举回文序列的头尾字符\n",
    "        ans = 0\n",
    "        for i, va in enumerate(s):\n",
    "            if ind[va] and ind[va][-1] > i:\n",
    "                length = dfs(i, ind[va][-1])\n",
    "                ans = max(ans, length)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 动态规划\n",
    "# 使用三维动态规划dp[i][j][k]表示s[i:j+1]中以ASCII码为k开头结尾的回文子序列长度\n",
    "# 使用前后缀的最大值维护以非k结尾的子序列长度，使得子序列符合题意\n",
    "class Solution1:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        lst = [ord(w) - ord('a') for w in s]\n",
    "        dp = [[[0] * 26 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for k in range(26):\n",
    "                dp[i][i + 1][k] = int(lst[i] == lst[i + 1] == k) * 2\n",
    "\n",
    "            for j in range(i + 2, n):\n",
    "                if lst[i] != lst[j]:\n",
    "                    for k in range(26):\n",
    "                        dp[i][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k])\n",
    "                else:\n",
    "                    cur = dp[i + 1][j - 1]\n",
    "                    pre = [0] * (26 + 1)\n",
    "                    post = [0] * (26 + 1)\n",
    "                    for x in range(26):\n",
    "                        pre[x + 1] = max(pre[x], cur[x])\n",
    "                        post[26 - x - 1] = max(post[26 - x], cur[26 - x - 1])\n",
    "\n",
    "                    for k in range(26):\n",
    "                        dp[i][j][k] = max(pre[k], post[k + 1]) + 2 * (lst[i] == k)\n",
    "\n",
    "        return max([max([max(x) for x in d]) for d in dp])\n",
    "\n",
    "\n",
    "\n",
    "# 记忆化搜索\n",
    "# 枚举首尾的字母进行递归记忆化搜索\n",
    "# 向内搜索的时候确保下一个字符与当前不同\n",
    "from functools import lru_cache\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        ind = defaultdict(list)\n",
    "        for i, va in enumerate(s):\n",
    "            ind[va].append(i)\n",
    "\n",
    "        # 记忆化搜索\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            res = 2\n",
    "            for r in range(x + 1, y):\n",
    "                if s[r] != s[x]:\n",
    "                    val = s[r]\n",
    "                    right = -1\n",
    "                    for rj in ind[val][::-1]:\n",
    "                        if rj < y:\n",
    "                            right = rj\n",
    "                            break\n",
    "\n",
    "                    left = -1\n",
    "                    for li in ind[val]:\n",
    "                        if li > x:\n",
    "                            left = li\n",
    "                            break\n",
    "\n",
    "                    if left < right and left != -1 and right != -1:\n",
    "                        res = max(res, 2 + dfs(left, right))\n",
    "\n",
    "            return res\n",
    "\n",
    "\n",
    "        # 枚举回文序列的头尾字符\n",
    "        ans = 0\n",
    "        for i, va in enumerate(s):\n",
    "            if ind[va] and ind[va][-1] > i:\n",
    "                length = dfs(i, ind[va][-1])\n",
    "                ans = max(ans, length)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # dp[i][j] 表示 i~j 最长的“好的回文子序列”的长度\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        # f[i][j] 表示 i-j 回文子序列最外围的字符\n",
    "        f = [['' for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for span in range(2, n+1): # 区间dp\n",
    "            for i in range(n-span+1):\n",
    "                j = i + span - 1\n",
    "\n",
    "                if s[i] == s[j] and s[i] != f[i+1][j-1]: # 满足条件：当前字母相同；且当前字母不等于内层回文序列的最外围字符\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                    f[i][j] = s[i] # 新的回文串，最外围字母更新为当前字母\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n",
    "                    f[i][j] = f[i+1][j] if dp[i+1][j] > dp[i][j-1] else f[i][j-1]\n",
    "        \n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # dp[i][j] 表示 i~j 最长的“好的回文子序列”的长度\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        # f[i][j] 表示 i-j 回文子序列最外围的字符\n",
    "        f = [['' for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for span in range(2, n+1): # 区间dp\n",
    "            for i in range(n-span+1):\n",
    "                j = i + span - 1\n",
    "\n",
    "                if s[i] == s[j] and s[i] != f[i+1][j-1]:\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                    f[i][j] = s[i]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n",
    "                    f[i][j] = f[i+1][j] if dp[i+1][j] > dp[i][j-1] else f[i][j-1]\n",
    "        \n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[[0,''] for _ in range(n)] for _ in range(n)]\n",
    "        ans = \"\"\n",
    "        for j in range(1,n):\n",
    "            for i in range(j-1,-1,-1):\n",
    "                if s[i] == s[j] and s[j] != f[i+1][j-1][1]:\n",
    "                    f[i][j][0] = f[i+1][j-1][0] + 2\n",
    "                    f[i][j][1] = s[j]\n",
    "                else:\n",
    "                    f[i][j] = f[i][j-1] if f[i][j-1][0] > f[i+1][j][0] else f[i+1][j]\n",
    "\n",
    "        return f[0][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[[0] * 26 for _ in range(n)] for _ in range(n)]\n",
    "        res = 0\n",
    "        for length in range(2, n+1):\n",
    "            for start in range(0, n - length + 1):\n",
    "                end = start + length - 1\n",
    "                for i in range(26):\n",
    "                    dp[start][end][i] = max(dp[start][end - 1][i], dp[start + 1][end][i])\n",
    "                if s[start] == s[end]:\n",
    "                    j = ord(s[start]) - 97\n",
    "                    for i in range(26):\n",
    "                        if i != j:\n",
    "                            dp[start][end][j] = max(dp[start][end][j], dp[start + 1][end - 1][i] + 2)\n",
    "                            res = max(res, dp[start][end][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 动态规划\n",
    "# 使用三维动态规划dp[i][j][k]表示s[i:j+1]中以ASCII码为k开头结尾的回文子序列长度\n",
    "# 使用前后缀的最大值维护以非k结尾的子序列长度，使得子序列符合题意\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        lst = [ord(w) - ord('a') for w in s]\n",
    "        dp = [[[0] * 26 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for k in range(26):\n",
    "                dp[i][i + 1][k] = int(lst[i] == lst[i + 1] == k) * 2\n",
    "\n",
    "            for j in range(i + 2, n):\n",
    "                if lst[i] != lst[j]:\n",
    "                    for k in range(26):\n",
    "                        dp[i][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k])\n",
    "                else:\n",
    "                    cur = dp[i + 1][j - 1]\n",
    "                    pre = [0] * (26 + 1)\n",
    "                    post = [0] * (26 + 1)\n",
    "                    for x in range(26):\n",
    "                        pre[x + 1] = max(pre[x], cur[x])\n",
    "                        post[26 - x - 1] = max(post[26 - x], cur[26 - x - 1])\n",
    "\n",
    "                    for k in range(26):\n",
    "                        dp[i][j][k] = max(pre[k], post[k + 1]) + 2 * (lst[i] == k)\n",
    "\n",
    "        return max([max([max(x) for x in d]) for d in dp])\n",
    "\n",
    "\n",
    "\n",
    "# 记忆化搜索\n",
    "# 枚举首尾的字母进行递归记忆化搜索\n",
    "# 向内搜索的时候确保下一个字符与当前不同\n",
    "from functools import lru_cache\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution2:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        ind = defaultdict(list)\n",
    "        for i, va in enumerate(s):\n",
    "            ind[va].append(i)\n",
    "\n",
    "        # 记忆化搜索\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            res = 2\n",
    "            for r in range(x + 1, y):\n",
    "                if s[r] != s[x]:\n",
    "                    val = s[r]\n",
    "                    right = -1\n",
    "                    for rj in ind[val][::-1]:\n",
    "                        if rj < y:\n",
    "                            right = rj\n",
    "                            break\n",
    "\n",
    "                    left = -1\n",
    "                    for li in ind[val]:\n",
    "                        if li > x:\n",
    "                            left = li\n",
    "                            break\n",
    "\n",
    "                    if left < right and left != -1 and right != -1:\n",
    "                        res = max(res, 2 + dfs(left, right))\n",
    "\n",
    "            return res\n",
    "\n",
    "\n",
    "        # 枚举回文序列的头尾字符\n",
    "        ans = 0\n",
    "        for i, va in enumerate(s):\n",
    "            if ind[va] and ind[va][-1] > i:\n",
    "                length = dfs(i, ind[va][-1])\n",
    "                ans = max(ans, length)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        occ = set(s)\n",
    "        que = defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            que[ch].append(i)\n",
    "        \n",
    "        @cache\n",
    "        def f(i, j, pre):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if s[i] == pre:\n",
    "                return f(i + 1, j, pre)\n",
    "            if s[j] == pre:\n",
    "                return f(i, j - 1, pre)\n",
    "            res = 0\n",
    "            for k in reversed(que[s[i]]):\n",
    "                if k <= j and k > i:\n",
    "                    res = 2 + f(i + 1, k - 1, s[i])\n",
    "                    break \n",
    "            for k in que[s[j]]:\n",
    "                if k >= i and k < j:\n",
    "                    res = max(res, 2 + f(k + 1, j - 1, s[j]))\n",
    "            res = max(res, f(i + 1, j - 1, pre))\n",
    "            return res \n",
    "        \n",
    "        return f(0, n - 1, '+')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j, last):\n",
    "            if i >= j: return 0\n",
    "            if s[i] == s[j] and s[i] != last:\n",
    "                return dfs(i + 1, j - 1, s[i]) + 2\n",
    "            return max(dfs(i + 1, j, last), dfs(i, j - 1, last))\n",
    "        res = dfs(0, len(s) - 1, None)\n",
    "        del dfs\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        # 简单，区间DP可以解决问题\n",
    "        # 怎样解决连续字符不相等的问题？\n",
    "        @cache\n",
    "        def f(i, j, last):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if s[i] == s[j] and s[i] != last:\n",
    "                return 2 + f(i+1, j-1, last=s[i])\n",
    "            return max(f(i+1, j, last), f(i, j-1, last))\n",
    "        ans = f(0, len(s)-1, '*')\n",
    "        f.cache_clear()\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        @cache\n",
    "        def f(L, R, p):\n",
    "            if L == R: return 0\n",
    "            rnt = max(f(L+1, R, p), f(L, R-1, p))\n",
    "            l, r = s.find(s[R-1], L, R), s.rfind(s[L], L, R)\n",
    "\n",
    "            if l != R-1 and s[R-1] != p:\n",
    "                rnt = max(rnt, 2 + f(l+1, R-1, s[R-1]))\n",
    "            if r != L and s[L] != p:\n",
    "                rnt = max(rnt, 2 + f(L+1, r, s[L]))\n",
    "            return rnt\n",
    "        \n",
    "        ans = f(0, len(s), \"-\")\n",
    "        f.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        NO_PREV = \"#\"\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, last: str) -> int:\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if s[i] == s[j] and s[i] != last:\n",
    "                return 2 + dfs(i + 1, j - 1, s[i])\n",
    "            return max(dfs(i + 1, j, last), dfs(i, j - 1, last))\n",
    "        \n",
    "        return dfs(0, len(s) - 1, NO_PREV)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
